//Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater
//than or equal to x.
//You should preserve the original relative order of the nodes in each of the two partitions.
//For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.


#include<iostream>

using namespace std;

template<typename T>
struct ListNode{
	T _value;
	ListNode<T> *_next;
	ListNode(T value)
		:_value(value),
		_next(NULL)
	{}
};

template<typename T>
class Solution{
public:
	void Partition(ListNode<T>*head, int x) //List not has phead ;
	{
		if (head == NULL)
		{
			return;
		}
		ListNode<T> *tmp = head;
		ListNode<T> *cur = head;
		ListNode<T> *prev = NULL;
		while (cur!= NULL)
		{
			if (cur->_value < x)
			{
				if (cur->_next ==tmp->_next)
				{
					;//donoting
				}
				else
				{
					if (prev == NULL)
					{
						;//donoting
					}
					else//exchange
					{
						ListNode<T> *exchange = cur;
					    prev->_next = cur->_next;
						exchange->_next = tmp->_next;
						tmp->_next = exchange;
						tmp = tmp->_next;
					}
				}
			}
				prev = cur;
				cur = cur->_next;
		}

	}
	void Display(ListNode<T> *head)
	{
		if (head == NULL)
		{
			return;
		}
		ListNode<T> *cur = head;
		while (cur!=NULL)
		{
			cout << cur->_value << "->";
			cur = cur->_next;
		}
		cout << "NULL";
	}
};


int main()
{
	ListNode<int> *head  = new ListNode<int>(1);
	ListNode<int> *list1 = new ListNode<int>(4);
	ListNode<int> *list2 = new ListNode<int>(3);
	ListNode<int> *list3 = new ListNode<int>(2);
	ListNode<int> *list4 = new ListNode<int>(5);
	ListNode<int> *list5 = new ListNode<int>(2);
	head->_next = list1;
	list1->_next = list2;
	list2->_next = list3;
	list3->_next = list4;
	list4->_next = list5;
	Solution<int> s;
	s.Partition(head,3);
	s.Display(head);
	return 0;
}